package 单调栈;

import org.junit.Test;

import java.util.*;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/2/14 16:43
 */
public class Note {

    /*
     单调栈 名字: 画一下  单调找 每个 元素的  函数 曲线图 (就明白 为什么 称为 单调栈 了! )
     */



    /*
   单调栈：给定 一个 数组 nums [] ,对于 每一个 数组内的下标 index,
   能不能 在 O(N) 的是按复杂度 生成  ** 左边 离 index 最近比 它小的 右边 同理 **
   注意这个流程;
   更加 注意 这里 存储的  是 index (下标)
    */


    /*
    单调栈 无重复值的 版本
    可以 用 二维 数组 存储
    因为 这里 操作的 全都是  元素的 下标 index


    ==
    卧槽了, Deque 相关 api 的理解 是 有问题的!
    理解 不到位 导致的 !

     */
    public static int[][] unrepeatElementVersion(int[] nums) {
        int[][] ans = new int[nums.length][2];
        Deque<Integer> stack = new ArrayDeque<>();
        int temp;
        // 添加 一些 简单的 过滤 不合理的东西
//        stack.push(0);
        for (int i = 0; i < nums.length; i++) {
             while(!stack.isEmpty() && nums[i] < nums[stack.peekLast()]){
                 temp = stack.pollLast();
                 ans[temp][0] = stack.isEmpty() ? - 1 : stack.peekLast();
                 ans[temp][1] = i;
             }
             stack.offerLast(i);
        }
        // stack maybe  not empty!
        while(!stack.isEmpty()){
            temp = stack.pollLast();
            ans[temp][1] = -1;
            ans[temp][0] = stack.isEmpty() ? - 1 : stack.peekLast();
        }
        return ans;
    }


//=============================================================================================
    /*
    还得 多写 写, 这个 单调栈的 代码
    还是 有很多coding 细节在里面的!
     */



    /*
     有重复 元素的 版本
     ,思考一下 使用 Node ,还是 数组 来存储这个 相同的元素
     下面这个 代码 很考验代码 的 coding 能力 ( 逻辑 非常的 多)
     */
    public int[][] repeatElementVersion(int[] nums) {
        int ans[][] = new int[nums.length][2];
        Deque<Deque<Integer>> stack = new ArrayDeque<>();
        for (int i = 0; i < nums.length; i++) {
            // 内层的 Deque 不需要 empty 判断!
            while (!stack.isEmpty() && nums[i] < nums[stack.peekLast().peekLast()]) {
                Deque<Integer> integers = stack.pollLast();
                /*
                 这里 整个 小的 优化
                 就是 提前 获取 leftIndex 的 值, 因为 这个 值 是固定的!
                 */
                int lfetIndex = stack.isEmpty() ? -1 : stack.peekLast().peekLast();
                while(!integers.isEmpty()){
                    int temp = integers.pollLast();
                    ans[temp][0] = lfetIndex;
                    ans[temp][1] = i;
                }
//                while (!integers.isEmpty()) {
//                    int temp = integers.pollLast();
//                    ans[temp][0] = stack.isEmpty() ? -1 : stack.peekLast().peekLast();
//                    ans[temp][1] = i;
//                }
            }
             /*
              走到 这里 有三种情况
              ①: equals
              ②: great than
              ③: stack is emptu
              ②③情况的 代码 是一样的 (最优尝试 也是 先写 ② ③)
              */
            if (stack.isEmpty() || nums[i] > nums[stack.peekLast().peekLast()]) {
                stack.offerLast(new ArrayDeque<>());
                stack.peekLast().offerLast(i);
            } else {
                stack.peekLast().offerLast(i);
            }
        }
        // 剩余的 未 出 栈的 元素
        while(!stack.isEmpty()){
            Deque<Integer> integers = stack.pollLast();
            while(!integers.isEmpty()){
                int temp = integers.pollLast();
                ans[temp][1] = -1;
                /*
                 同理 这里的 lfetIndex 也可以 提前 算出 来, 这里 就不写了!
                 */
                ans[temp][0] = stack.isEmpty() ? -1 : stack.peekLast().peekLast();
            }
        }

        return ans;
    }


    public static void main(String[] args) {
        int nums[] = {3,4,2,6,1,7,0,5};
        int[][] ints = unrepeatElementVersion(nums);
        for(int num[] : ints){
            System.out.println(Arrays.toString(num));
        }
        System.out.println("=========================");

        for(int nums1[] : function(nums)){
            System.out.println(Arrays.toString(nums1));
        }

    }


    @Test
    public void test(){
//        int nums[] = {2,2,2,1,1,1};
//        int nums[] = {3,4,3,4,3,2,2};
        int nums[] = {2,3,4,3,4,3,2};
        int[][] ints = repeatElementVersion(nums);
        for(int[] num : ints){
            System.out.println(Arrays.toString(num));
        }

        System.out.println( " ============================================ ");
        int[][] ints1 = repeatElementVersionSimplify(nums);
        for(int[] num : ints1){
            System.out.println(Arrays.toString(num));
        }



    }



    /*
     2023/3/12
     考虑的是没有重复元素的情况
     写的 没什么毛病!
     */
    public static int[][]function(int nums[]){
        int index[][] = new int[nums.length][2];
        Deque<Integer> stack = new ArrayDeque<>();
        for(int i = 0;i < nums.length;i++ ){
                // 好像可以省略
//            if(stack.isEmpty() || nums[stack.peekLast()] < nums[i]){
//                stack.addLast(i);
//                continue;
//            }
            while(!stack.isEmpty() && nums[stack.peekLast()] > nums[i]){
                int temp = stack.removeLast();
                index[temp][0] = stack.isEmpty() ? -1 : stack.peekLast();
                index[temp][1] = i;
            }
            stack.addLast(i);

        }

        // 对栈中 余留的元素进行单独的处理
        while(!stack.isEmpty()){
            int temp = stack.removeLast();
            index[temp][0] = stack.isEmpty() ? - 1 : stack.peekLast();
            index[temp][1] = -1;
        }
        return index;
    }

    /*
    -- 这里标注  一下：  下面这种做法 是错的， 还是得 用 list 来存储 相同的元素
        但是 如果 只是 **求 下一个 系列版本的 话， 下面的做法 是正确的**
        **但是 你要求 上一个  最近 大（小） 的就是错的**

    比如下面这个 case ：
    int nums[] = {2,3,4,3,4,3,2};
     有重复元素 的一个 简化的版本, 根本就不需要
     使用 list 或者 queue, 直接 入栈 就行了
     不过在最后 判断的时候需要 , 改变一下!
 */
    public static int[][] repeatElementVersionSimplify(int[] nums) {
        int[][] ans = new int[nums.length][2];
        Deque<Integer> stack = new ArrayDeque<>();
        int temp;
        // 添加 一些 简单的 过滤 不合理的东西
//        stack.push(0);
        for (int i = 0; i < nums.length; i++) {
            while(!stack.isEmpty() && nums[i] < nums[stack.peekLast()]){
                temp = stack.pollLast();
                ans[temp][0] = stack.isEmpty() || nums[temp] == nums[stack.peekLast()] ? - 1 : stack.peekLast();
                ans[temp][1] = i;
            }
            stack.offerLast(i);
        }
        // stack maybe  not empty!
        while(!stack.isEmpty()){
            temp = stack.pollLast();
            ans[temp][1] = -1;
            ans[temp][0] = stack.isEmpty() || nums[temp] == nums[stack.peekLast()] ? - 1 : stack.peekLast();
        }
        return ans;
    }



}
